# CPU Scheduling


# 1. ์Šค์ผ€์ค„๋ง

CPU ๋ฅผ ์ž˜ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด ํ”„๋กœ์„ธ์Šค๋ฅผ ์ž˜ ๋ฐฐ์ •ํ•˜๊ธฐ

  • ์กฐ๊ฑด : ์˜ค๋ฒ„ํ—ค๋“œ โ†“ / ์‚ฌ์šฉ๋ฅ  โ†‘ / ๊ธฐ์•„ ํ˜„์ƒ โ†“
  • ๋ชฉํ‘œ
    1. Batch System: ๊ฐ€๋Šฅํ•˜๋ฉด ๋งŽ์€ ์ผ์„ ์ˆ˜ํ–‰. ์‹œ๊ฐ„(time) ๋ณด๋‹จ ์ฒ˜๋ฆฌ๋Ÿ‰(throughout)์ด ์ค‘์š”
    2. Interactive System: ๋น ๋ฅธ ์‘๋‹ต ์‹œ๊ฐ„. ์ ์€ ๋Œ€๊ธฐ ์‹œ๊ฐ„.
    3. Real-time System: ๊ธฐํ•œ(deadline) ๋งž์ถ”๊ธฐ.

# 2. ์„ ์  / ๋น„์„ ์  ์Šค์ผ€์ค„๋ง

  • ์„ ์  (preemptive) : OS๊ฐ€ CPU์˜ ์‚ฌ์šฉ๊ถŒ์„ ์„ ์ ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, ๊ฐ•์ œ ํšŒ์ˆ˜ํ•˜๋Š” ๊ฒฝ์šฐ (์ฒ˜๋ฆฌ์‹œ๊ฐ„ ์˜ˆ์ธก ์–ด๋ ค์›€)
  • ๋น„์„ ์  (nonpreemptive) : ํ”„๋กœ์„ธ์Šค ์ข…๋ฃŒ or I/O ๋“ฑ์˜ ์ด๋ฒคํŠธ๊ฐ€ ์žˆ์„ ๋•Œ๊นŒ์ง€ ์‹คํ–‰ ๋ณด์žฅ (์ฒ˜๋ฆฌ์‹œ๊ฐ„ ์˜ˆ์ธก ์šฉ์ดํ•จ)

# 3. ํ”„๋กœ์„ธ์Šค ์ƒํƒœ

download (5)

  • ์„ ์  ์Šค์ผ€์ค„๋ง : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
  • ๋น„์„ ์  ์Šค์ผ€์ค„๋ง : I/O or Event Wait, Exit

ํ”„๋กœ์„ธ์Šค์˜ ์ƒํƒœ ์ „์ด

โœ“ย ์Šน์ธ (Admitted)ย : ํ”„๋กœ์„ธ์Šค ์ƒ์„ฑ์ด ๊ฐ€๋Šฅํ•˜์—ฌ ์Šน์ธ๋จ.

โœ“ย ์Šค์ผ€์ค„๋Ÿฌ ๋””์ŠคํŒจ์น˜ (Scheduler Dispatch)ย : ์ค€๋น„ย ์ƒํƒœ์— ์žˆ๋Š” ํ”„๋กœ์„ธ์Šค ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•˜์—ฌ ์‹คํ–‰์‹œํ‚ค๋Š” ๊ฒƒ.

โœ“ย ์ธํ„ฐ๋ŸฝํŠธ (Interrupt)ย :ย ์˜ˆ์™ธ,ย ์ž…์ถœ๋ ฅ, ์ด๋ฒคํŠธ ๋“ฑ์ด ๋ฐœ์ƒํ•˜์—ฌ ํ˜„์žฌ ์‹คํ–‰ย ์ค‘์ธ ํ”„๋กœ์„ธ์Šค๋ฅผ ์ค€๋น„ ์ƒํƒœ๋กœ ๋ฐ”๊พธ๊ณ , ํ•ด๋‹น ์ž‘์—…์„ ๋จผ์ € ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ.

โœ“ย ์ž…์ถœ๋ ฅ ๋˜๋Š” ์ด๋ฒคํŠธ ๋Œ€๊ธฐ (I/O or Event wait)ย : ์‹คํ–‰ ์ค‘์ธย ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž…์ถœ๋ ฅ์ด๋‚˜ ์ด๋ฒคํŠธ๋ฅผ ์ฒ˜๋ฆฌํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ, ์ž…์ถœ๋ ฅ/์ด๋ฒคํŠธ๊ฐ€ ๋ชจ๋‘ ๋๋‚  ๋•Œ๊นŒ์ง€ ๋Œ€๊ธฐ ์ƒํƒœ๋กœ ๋งŒ๋“œ๋Š” ๊ฒƒ.

โœ“ย ์ž…์ถœ๋ ฅ ๋˜๋Š” ์ด๋ฒคํŠธ ์™„๋ฃŒ (I/O or Event Completion)ย : ์ž…์ถœ๋ ฅ/์ด๋ฒคํŠธ๊ฐ€ ๋๋‚œ ํ”„๋กœ์„ธ์Šค๋ฅผ ์ค€๋น„ ์ƒํƒœ๋กœ ์ „ํ™˜ํ•˜์—ฌ ์Šค์ผ€์ค„๋Ÿฌ์— ์˜ํ•ด ์„ ํƒ๋  ์ˆ˜ ์žˆ๋„๋ก ๋งŒ๋“œ๋Š” ๊ฒƒ.

# 4. CPU ์Šค์ผ€์ค„๋ง์˜ ์ข…๋ฅ˜

  • ๋น„์„ ์  ์Šค์ผ€์ค„๋ง

    1. FCFS (First Come First Served)
      • ํ์— ๋„์ฐฉํ•œ ์ˆœ์„œ๋Œ€๋กœ CPU ํ• ๋‹น
      • ์‹คํ–‰ ์‹œ๊ฐ„์ด ์งง์€ ๊ฒŒ ๋’ค๋กœ ๊ฐ€๋ฉด ํ‰๊ท  ๋Œ€๊ธฐ ์‹œ๊ฐ„์ด ๊ธธ์–ด์ง
    2. SJF (Shortest Job First)
      • ์ˆ˜ํ–‰์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์งง๋‹ค๊ณ  ํŒ๋‹จ๋˜๋Š” ์ž‘์—…์„ ๋จผ์ € ์ˆ˜ํ–‰
      • FCFS ๋ณด๋‹ค ํ‰๊ท  ๋Œ€๊ธฐ ์‹œ๊ฐ„ ๊ฐ์†Œ, ์งง์€ ์ž‘์—…์— ์œ ๋ฆฌ
    3. HRN (Hightest Response-ratio Next)
      • ์šฐ์„ ์ˆœ์œ„๋ฅผ ๊ณ„์‚ฐํ•˜์—ฌ ์ ์œ  ๋ถˆํ‰๋“ฑ์„ ๋ณด์™„ํ•œ ๋ฐฉ๋ฒ•(SJF์˜ ๋‹จ์  ๋ณด์™„)
      • ์šฐ์„ ์ˆœ์œ„ = (๋Œ€๊ธฐ์‹œ๊ฐ„ + ์‹คํ–‰์‹œ๊ฐ„) / (์‹คํ–‰์‹œ๊ฐ„)
  • ์„ ์  ์Šค์ผ€์ค„๋ง

    1. Priority Scheduling

      • ์ •์ /๋™์ ์œผ๋กœ ์šฐ์„ ์ˆœ์œ„๋ฅผ ๋ถ€์—ฌํ•˜์—ฌ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌ
      • ์šฐ์„  ์ˆœ์œ„๊ฐ€ ๋‚ฎ์€ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฌดํ•œ์ • ๊ธฐ๋‹ค๋ฆฌ๋Š” Starvation ์ด ์ƒ๊ธธ ์ˆ˜ ์žˆ์Œ
      • Aging ๋ฐฉ๋ฒ•์œผ๋กœ Starvation ๋ฌธ์ œ ํ•ด๊ฒฐ ๊ฐ€๋Šฅ
    2. Round Robin

      • FCFS์— ์˜ํ•ด ํ”„๋กœ์„ธ์Šค๋“ค์ด ๋ณด๋‚ด์ง€๋ฉด ๊ฐ ํ”„๋กœ์„ธ์Šค๋Š” ๋™์ผํ•œ ์‹œ๊ฐ„์˜ Time Quantum ๋งŒํผ CPU๋ฅผ ํ• ๋‹ฌ ๋ฐ›์Œ
        • Time Quantum or Time Slice : ์‹คํ–‰์˜ ์ตœ์†Œ ๋‹จ์œ„ ์‹œ๊ฐ„
      • ํ• ๋‹น ์‹œ๊ฐ„(Time Quantum)์ด ํฌ๋ฉด FCFS์™€ ๊ฐ™๊ฒŒ ๋˜๊ณ , ์ž‘์œผ๋ฉด ๋ฌธ๋งฅ ๊ตํ™˜ (Context Switching) ์žฆ์•„์ ธ์„œ ์˜ค๋ฒ„ํ—ค๋“œ ์ฆ๊ฐ€
    3. Multilevel-Queue (๋‹ค๋‹จ๊ณ„ ํ)

      Untitled1

      • ์ž‘์—…๋“ค์„ ์—ฌ๋Ÿฌ ์ข…๋ฅ˜์˜ ๊ทธ๋ฃน์œผ๋กœ ๋‚˜๋ˆ„์–ด ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ธฐ๋ฒ• Untitled

      • ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋‚ฎ์€ ํ๋“ค์ด ์‹คํ–‰ ๋ชปํ•˜๋Š” ๊ฑธ ๋ฐฉ์ง€ํ•˜๊ณ ์ž ๊ฐ ํ๋งˆ๋‹ค ๋‹ค๋ฅธ Time Quantum์„ ์„ค์ • ํ•ด์ฃผ๋Š” ๋ฐฉ์‹ ์‚ฌ์šฉ

      • ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ํ๋Š” ์ž‘์€ Time Quantum ํ• ๋‹น. ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋‚ฎ์€ ํ๋Š” ํฐ Time Quantum ํ• ๋‹น.

    4. Multilevel-Feedback-Queue (๋‹ค๋‹จ๊ณ„ ํ”ผ๋“œ๋ฐฑ ํ)

      Untitled2

      • ๋‹ค๋‹จ๊ณ„ ํ์—์„œ ์ž์‹ ์˜ Time Quantum์„ ๋‹ค ์ฑ„์šด ํ”„๋กœ์„ธ์Šค๋Š” ๋ฐ‘์œผ๋กœ ๋‚ด๋ ค๊ฐ€๊ณ  ์ž์‹ ์˜ Time Quantum์„ ๋‹ค ์ฑ„์šฐ์ง€ ๋ชปํ•œ ํ”„๋กœ์„ธ์Šค๋Š” ์›๋ž˜ ํ ๊ทธ๋Œ€๋กœ
        • Time Quantum์„ ๋‹ค ์ฑ„์šด ํ”„๋กœ์„ธ์Šค๋Š” CPU burst ํ”„๋กœ์„ธ์Šค๋กœ ํŒ๋‹จํ•˜๊ธฐ ๋•Œ๋ฌธ
      • ์งง์€ ์ž‘์—…์— ์œ ๋ฆฌ, ์ž…์ถœ๋ ฅ ์œ„์ฃผ(Interrupt๊ฐ€ ์žฆ์€) ์ž‘์—…์— ์šฐ์„ ๊ถŒ์„ ์คŒ
      • ์ฒ˜๋ฆฌ ์‹œ๊ฐ„์ด ์งง์€ ํ”„๋กœ์„ธ์Šค๋ฅผ ๋จผ์ € ์ฒ˜๋ฆฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— Turnaround ํ‰๊ท  ์‹œ๊ฐ„์„ ์ค„์˜‚์คŒ

# 5. CPU ์Šค์ผ€์ค„๋ง ์ฒ™๋„

  1. Response Time
    • ์ž‘์—…์ด ์ฒ˜์Œ ์‹คํ–‰๋˜๊ธฐ๊นŒ์ง€ ๊ฑธ๋ฆฐ ์‹œ๊ฐ„
  2. Turnaround Time
    • ์‹คํ–‰ ์‹œ๊ฐ„๊ณผ ๋Œ€๊ธฐ ์‹œ๊ฐ„์„ ๋ชจ๋‘ ํ•ฉํ•œ ์‹œ๊ฐ„์œผ๋กœ ์ž‘์—…์ด ์™„๋ฃŒ๋  ๋•Œ ๊นŒ์ง€ ๊ฑธ๋ฆฐ ์‹œ๊ฐ„

# ์ถœ์ฒ˜

์ตœ์ข… ์ˆ˜์ • : 12/17/2022, 7:23:59 AM